package com.cuz.daileetcode;

import com.cuz.daileetcode.utils.ArrayUtils;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Random;

public class Day64 {


    public static int solution1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        Arrays.sort(arr);
        int max = Integer.MIN_VALUE;
        for (int index = 1; index < arr.length; index++) {
            max = Math.max(arr[index] - arr[index - 1], max);
        }
        return max;
    }

    public static void main(String[] args) {
//        int[] arr1 = {1, 2, 5, 7, 10, 20, 17, 40};
//        int[] arr2 = Arrays.copyOf(arr1, arr1.length);
//        System.out.println(solution1(arr1));
//        ArrayUtils.print(arr1);
//        System.out.println(solution2(arr2));

        for (int i = 100; i > 0; i--) {
            int[] ints = randomArray(new Random().nextInt(1000));
            int[] ints2 = Arrays.copyOf(ints, ints.length);
            if (solution2(ints) != solution1(ints2)) {
                ArrayUtils.print(ints2);
                break;
            }
        }
    }

    private static int[] randomArray(int i) {
        Random r = new Random();
        int[] arr = new int[i];
        for (int index = arr.length - 1; index >= 0; index--) {
            arr[index] = r.nextInt(1000);
        }
        return arr;
    }

    public static int solution2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int len = arr.length;
        for (int index = 0; index < len; index++) {
            max = Math.max(max, arr[index]);
            min = Math.min(min, arr[index]);
        }
        boolean[] hasNumArray = new boolean[len + 1];
        int[] maxNumArray = new int[len + 1];
        int[] minNumArray = new int[len + 1];
        if (max == min) {
            return 0;
        }
        for (int index = 0; index < len; index++) {
            int bucketIndex = bucketShouldBe(arr[index], max, min, len);
            if (hasNumArray[bucketIndex]) {
                maxNumArray[bucketIndex] = Math.max(maxNumArray[bucketIndex], arr[index]);
                minNumArray[bucketIndex] = Math.min(minNumArray[bucketIndex], arr[index]);
            } else {
                maxNumArray[bucketIndex] = arr[index];
                minNumArray[bucketIndex] = arr[index];
            }
            hasNumArray[bucketIndex] = true;

        }
        int res = 0;
        int preMax = maxNumArray[0];
        for (int index = 1; index <= len; index++) {
            if (hasNumArray[index]) {
                res = Math.max(res, minNumArray[index] - preMax);
                preMax = maxNumArray[index];
            }
        }
        return res;
    }

    private static int bucketShouldBe(int value, long max, long min, long len) {
        return (int) ((value - min) * len / (max - min));
    }


    private static int solution3(int[] arr) {
        //异或和
        int xorSum = 0;
        //dp[i] arr[i]结尾的数组最优划分的数目
        int[] dp = new int[arr.length];
        //记录异或和为key最近出现的位置value
        HashMap<Integer, Integer> preXorSumIndexMap = new HashMap<>();
        //默认0出现在 -1 位置
        preXorSumIndexMap.put(0, -1);
        for (int index = 0; index < arr.length; index++) {
            //更新异或和
            xorSum = xorSum ^ arr[index];
            //上一次这个异或和出现在什么位置
            Integer preXorSumEqualIndex = preXorSumIndexMap.get(xorSum);
            //如果出现过，index位置的数参与到最优划分
            if (preXorSumEqualIndex != null) {
                //为-1 表示 xorSum=0 那么这个位置就是一个左右划分
                // 0 1 2 这个0单独构成最优划分
                if (preXorSumEqualIndex == -1) {
                    dp[index] = 1;
                } else {
                    //否则为之前加1
                    //4 0  3  0  |3  2   1|
                    //3 2 1构成最优
                    dp[index] = dp[preXorSumEqualIndex] + 1;
                }
            }
            //index的数不参与到最优划分
            if (index > 0) {
                //3 2 1  |4|  4不参与
                dp[index] = Math.max(dp[index - 1], dp[index]);
            }
            //更新map 记录最近出现的位置
            preXorSumIndexMap.put(xorSum, index);
        }
        return dp[arr.length - 1];
    }
}
